package com.leetcode.partition9;

import java.io.*;
import java.util.PriorityQueue;

/**
 * @author `RKC`
 * @date 2022/1/6 9:50
 */
public class LC847访问所有节点的最短路径idaStar {

    private static final int N = 13, INF = 0x3f3f3f3f;
    private static int[][] graph;
    private static boolean[][] visited;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(reader.readLine());
        int[][] graph = new int[n][];
        for (int i = 0; i < n; i++) {
            String[] s = reader.readLine().split("\\s+");
            int[] g = new int[s.length];
            for (int j = 0; j < s.length; j++) g[j] = Integer.parseInt(s[j]);
            graph[i] = g;
        }
        writer.write(shortestPathLength(graph) + "\n");
        writer.flush();
    }

    public static int shortestPathLength(int[][] g) {
        graph = g;
        int n = graph.length, answer = INF;
        visited = new boolean[n][1 << n];
        for (int i = 0; i < n; i++) {
            //以每一个节点进行迭代加深
            int maxDepth = 0;
            while (!idaStar(i, 1 << i, 0, maxDepth)) maxDepth++;
            answer = Math.min(answer, maxDepth);
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 1 << n; k++) {
                    visited[j][k] = false;
                }
            }
        }
        return answer;
    }

    private static boolean idaStar(int u, int status, int depth, int maxDepth) {
        if (eval(status) + depth > maxDepth) return false;
        if (eval(status) == 0) return true;
        //以当前节点出发访问周围的节点
        for (int v : graph[u]) {
            int nextStatus = status | 1 << v;
            if (visited[v][nextStatus]) continue;
            visited[v][nextStatus] = true;
            if (idaStar(v, nextStatus, depth + 1, maxDepth)) return true;
            visited[v][nextStatus] = false;
        }
        return false;
    }

    private static int eval(int status) {
        //估价函数，当前状态和全1状态的区别作为代价
        int res = 0;
        for (int i = 0; i < graph.length; i++) {
            if ((status >> i & 1) == 0) res++;
        }
        return res;
    }
}
